package Q589.II

import java.util.*
import kotlin.collections.ArrayList
import java.util.Stack

/**
 * @author23737
 * @data 2022.4.26
 * n叉树的前序遍历
 */
class Main {

}

fun main() {

}


class Node(var `val`: Int) {
    var children: List<Node?> = listOf()
}


class Solution {
    /**
     * 这是迭代写法
     */
    fun preorder(root: Node?): List<Int> {
        val res: MutableList<Int> = ArrayList<Int>()
        if (root == null) {
            return res
        }
        var stack = Stack<Node>()
        stack.push(root)
        while (!stack.isEmpty()) {
            var pop = stack.pop()
            res.add(pop.`val`)
            for (i in pop.children.indices.reversed()) {
                stack.push(pop.children[i])
            }
        }
        return res
    }

    /**
     * 这是递归写法
     */
    val res: MutableList<Int> = ArrayList<Int>()
    fun preorder2(root: Node?): List<Int> {
        if(root == null){
            return res
        }
        res.add(root.`val`)
        for(i in root.children){
            preorder2(i)
        }
        return res
    }
}
